package com.leetcode.LeetCode精选TOP面试题;

import java.util.ArrayList;
import java.util.List;

/**
 * @author 覃国强
 * @date 2022-05-24 11:46
 */
public class 题库_0046_全排列 {

  static
  class Solution {
    public List<List<Integer>> permute(int[] nums) {
      if (nums == null || nums.length == 0) {
        return new ArrayList<>();
      }
      List<List<Integer>> answers = new ArrayList<>();
//      backtrackWithSign(answers, nums, 0, new int[nums.length], new boolean[nums.length]);
      backtrackWithSwap(answers, nums, 0);
      return answers;
    }

    /**
     * 交换法，递归过程中不断交换 nums 中的数字用于区分已选数字和未选数字
     * [0, index - 1] 表示已选数字
     * [index, nums.length - 1] 表示未选数字
     * index 表示当前正在选择的数字位置
     * @param answers
     * @param nums
     * @param index
     */
    private void backtrackWithSwap(List<List<Integer>> answers, int[] nums, int index) {
      if (index == nums.length) {
        List<Integer> answer = new ArrayList<>();
        for (int num : nums) {
          answer.add(num);
        }
        answers.add(answer);
        return;
      }

      for (int i = index; i < nums.length; ++i) {
        swap(nums, i, index);
        backtrackWithSwap(answers, nums, index + 1);
        swap(nums, i, index);
      }
    }

    private void swap(int[] nums, int i, int j) {
      if (i != j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
      }
    }

    /**
     * 标记法，递归过程中标记已经使用过的数字
     * @param answers
     * @param nums
     * @param index
     * @param temp
     * @param sign
     */
    private void backtrackWithSign(List<List<Integer>> answers, int[] nums, int index, int[] temp, boolean[] sign) {
      if (index == nums.length) {
        List<Integer> answer = new ArrayList<>();
        for (int num : temp) {
          answer.add(num);
        }
        answers.add(answer);
        return;
      }

      for (int i = 0; i < nums.length; ++i) {
        if (!sign[i]) {
          sign[i] = true;
          temp[index] = nums[i];
          backtrackWithSign(answers, nums, index + 1, temp, sign);
          sign[i] = false;
        }
      }
    }
  }

}
